'''
@author: Kevin Zhao
@data:Feb 27 ,2013
@note:
Dynamic Programming

Exercise 15.1-3
'''

import sys
CUT_COST = 5#cutting cost
p = [0,1,5,8,9,10,17,17,20,24,30]#CLRS p.360
 
'''
Exercise 15.1-3(A)
Top-Down version of DP for rod-cutting
@var p:price array
     n:length of the rod
'''


def memorized_cut_rod(p,n):
    r = [-sys.maxint]*(n+1)#revenue array
    return memorized_cut_rod_aux(p,n,r)

def memorized_cut_rod_aux(p,n,r):
    q = 0
    if r[n] >= 0:
        return r[n]
    if n == 0:
        q = 0
    else:
#        q = -sys.maxint
        q = p[n]
        for i in range(1,n):
            q = max(q,p[i]+memorized_cut_rod_aux(p, n - i, r))
            if p[n] < q:
                q = q + CUT_COST 
    r[n] = q
    return q


print "_____________________TOP DOWN DP______________________"
print memorized_cut_rod(p,1)
print memorized_cut_rod(p,2)
print memorized_cut_rod(p,3)
print memorized_cut_rod(p,4)
print memorized_cut_rod(p,5)
print memorized_cut_rod(p,6)
print memorized_cut_rod(p,7)
print memorized_cut_rod(p,8)
print memorized_cut_rod(p,9)
print memorized_cut_rod(p,10)


 
'''
Exercise 15.1-3(B)
Bottom-up version of DP for rod-cutting
@var p:price array
     n:length of the rod
'''

def bottom_up_cut_rod(p,n):
    r = [-sys.maxint]*(n+1)#revenue array
    r[0] = 0
    r[1] = p[1]
    for j in range(1,n+1):
        q = p[j]
        for i in range(1,j):
            q = max(q,p[i]+r[j-i])
            if p[j] < q:
                q = q + CUT_COST 
        r[j] = q
    return r[n]
print "_____________________BOTTOM UP DP______________________"
print bottom_up_cut_rod(p,1)
print bottom_up_cut_rod(p,2)
print bottom_up_cut_rod(p,3)
print bottom_up_cut_rod(p,4)
print bottom_up_cut_rod(p,5)
print bottom_up_cut_rod(p,6)
print bottom_up_cut_rod(p,7)
print bottom_up_cut_rod(p,8)
print bottom_up_cut_rod(p,9)
print bottom_up_cut_rod(p,10)
